class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int left=0;
        int right=n-1;
        vector<int> tmp(n);
        for(int i=0;i<n;++i)
        {
            if(nums[i]==0)
            {
                tmp[left++]=0;
            }
            else if(nums[i]==2)
            {
                tmp[right--]=2;
            }
        }
        while(left<=right)
        {
            tmp[left++]=1;
        }
        for(int i=0;i<n;++i)
        {
            nums[i]=tmp[i];
        }
    }
};
